1. Field of the Invention
The present invention relates in general to the field of processors, and in particular, to a method and apparatus for providing a cache management technique.
2. Description of the Related Art
The use of a cache memory with a processor facilitates the reduction of memory access time. The fundamental idea of cache organization is that by keeping the most frequently accessed instructions and data in the fast cache memory, the average memory access time will approach the access time of the cache. To achieve the maximum possible speed of operation, typical processors implement a cache hierarchy, that is, different levels of cache memory. The different levels of cache correspond to different distances from the processor core. The closer the cache is to the processor, the faster the data access. However, the faster the data access, the more costly it is to store data. As a result, the closer the cache level, the faster and smaller the cache.
The performance of cache memory is frequently measured in terms of its hit ratio. When the processor refers to memory and finds the word in cache, it is said to produce a hit. If the word is not found in cache, then it is in main memory and it counts as a miss. If a miss occurs, then an allocation is made at the entry indexed by the access. The access can be for loading data to the processor or storing data from the processor to memory. The cached information is retained by the cache memory until it is no longer needed, made invalid or replaced by other data, in which instances the cache entry is de-allocated.
The type of data that is typically stored in cache includes active portions of programs and data. When the cache is full, it is necessary to replace existing lines of stored data in the cache memory to make room for newly requested lines of data. One such replacement technique involves the use of the least recently used (LRU) algorithm, which replaces the least recently used line of data with the newly requested line.
In cache memories that are organized using a set associative architecture, the LRU algorithm is used to maintain a list of the age of each way on a per set basis. The ages typically range from the most recently used to the least recently used. When a new element is written into a selected way, the age of the way is updated to indicate that it is the most recently used. In addition, when there is a cache hit, the age of the way that was hit also is updated to indicate that it is the most recently used. In applying the LRU algorithm, the data that is new or used repeatedly is frequently updated, so that its age is furthest from the least recently used data. As a result, frequently used data is unlikely to be evicted. However, if a new element is used once or infrequently, it will remain in the cache until it is the least recently used element. During this time, many reusable entries may have been evicted even if it would have been better to evict the infrequently used element. Since the infrequently used element will not be used again, it is truly the most eligible target for eviction.
For example, assume a cache set with two ways, one with data A and another with data B. Assume further that data A, data B, and data C target the same cache set and a program that reads and writes data A and data B multiple times. In the middle of the reads and writes of data A and data B, if the program performs an access of non-reusable data C, the cache will have to evict, for example, data A from way one and replace it with data C. If the program then tries to access data A again, a cache "miss" occurs, in which case data A is retrieved from external memory and data B is evicted from way two and replaced with data A. If the program then tries to access data B again, another cache "miss" occurs, in which case data B is retrieved from external memory and data C is evicted from way one and replaced with data B. Since data C is non-reusable by the program, this procedure wastes a considerable amount of clock cycles, decreases efficiency, and pollutes the cache.
Accordingly, there is a need in the technology for providing a cache management technique.